package cn.sjtu.algorithm.union_search_set;

/**
 * @author syo 2319615164@qq.com
 * @description 并查集
 * @date 2024/5/16
 * @Copyright syo
 */
public class UnionSearchSet {
    // 记录父节点
    public int[] parent;

    // 还有几个独立的集合
    public int count;

    // 以i为根节点的集合中的节点数量（注意只有根节点是有意义的）
    public int[] size;

    // 构造函数
    public UnionSearchSet(int size) {
        this.count = size;
        parent = new int[size + 1];
        this.size = new int[size + 1];
        for (int i = 1; i <= size; i++) {
            parent[i] = i;
            this.size[i] = 1;
        }
    }

    // 查找一个元素所属的集合
    public int find(int index) {
        if (parent[index] == index) {
            return index;
        } else {
            int res = find(parent[index]);
            parent[index] = res;
            return res;
        }
    }

    // 合并两个元素到一个集合
    public void union(int index1, int index2) {
        int parent1 = find(index1);
        int parent2 = find(index2);
        if (parent2 != parent1) {
            parent[parent2] = parent1;
            size[parent1] += size[parent2];
            count--;
        }
    }
}
